package basic.study.wantOffer.chapter5;

import java.util.ArrayDeque;

/**
 * @ClassName Problem59
 * @Description 队列的最大值
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/13 19:48
 * @Version 1.0
 */
public class Problem59 {
    /**
     * 滑动窗口的最大值
     */
    class Problem59_1 {
       ArrayDeque<Integer> deque = new ArrayDeque<>();
       int[] nums;

       public int[] maxSlidingWindow(int[] nums, int k) {
           int n = nums.length;
           if (n * k == 0) return nums;
           if (k == 1) return nums;

           //初始化
           int maxIndex = 0;
           for (int i = 0; i < k; i++) {
               cleanDeq(i, k);
               deque.addLast(i);
               if (nums[i] > nums[maxIndex]) maxIndex = i;
           }
           int[] output = new int[n - k + 1];
           output[0] = nums[maxIndex];

           //开始滑动
           for (int i = k; i < n; i++) {
               cleanDeq(i, k);
               deque.addLast(i);
               output[i - k +1] = nums[deque.getFirst()];
           }

           return output;
       }

        private void cleanDeq(int i, int k) {
            //首先去除超出窗口的
            while (!deque.isEmpty() && deque.getFirst() == i - k) {
                deque.removeFirst();
            }
            //然后去除小于当前插入值的
            while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
                deque.removeLast();
            }
        }
    }

    /**
     * 队列的最大值
     */
    static class Problem59_2 {
        ArrayDeque<InternalData> data = new ArrayDeque<>();
        ArrayDeque<InternalData> maximum = new ArrayDeque<>();
        int cur_index;

        public void push_back(int num) {
            InternalData curData = new InternalData(num, cur_index);
            data.addLast(curData);

            while (!maximum.isEmpty() && maximum.getLast().val < num) {
                maximum.removeLast();
            }
            maximum.addLast(curData);

            cur_index++;
        }

        public void pop_front() {
            if (data.isEmpty()) {
                System.out.println("队列为空，无法删除！");
                return;
            }
            InternalData curData = data.removeFirst();
            if (curData.index == maximum.getFirst().index) {
                maximum.removeFirst();
            }
        }

        public int max() {
            if (maximum.isEmpty()) {
                System.out.println("队列为空，无法删除");
                return 0;
            }
            return maximum.getFirst().val;
        }

        class InternalData {
            int val;
            int index;
            public InternalData(int val, int index) {
                this.val = val;
                this.index = index;
            }
        }
    }

    public static void main(String[] args) {
        Problem59_2 testQueue  = new Problem59_2();
        // {2}
        testQueue.push_back(2);
        System.out.println(testQueue.max()==2);
        // {2, 3}
        testQueue.push_back(3);
        System.out.println(testQueue.max()==3);
        // {2, 3, 4}
        testQueue.push_back(4);
        System.out.println(testQueue.max()==4);
        // {2, 3, 4, 2}
        testQueue.push_back(2);
        System.out.println(testQueue.max()==4);
        // {3, 4, 2}
        testQueue.pop_front();
        System.out.println(testQueue.max()==4);
        // {4, 2}
        testQueue.pop_front();
        System.out.println(testQueue.max()==4);
        // {2}
        testQueue.pop_front();
        System.out.println(testQueue.max()==2);
        // {2, 6}
        testQueue.push_back(6);
        System.out.println(testQueue.max()==6);
        // {2, 6, 2}
        testQueue.push_back(2);
        System.out.println(testQueue.max()==6);
        // {2, 6, 2, 5}
        testQueue.push_back(5);
        System.out.println(testQueue.max()==6);
        // {6, 2, 5}
        testQueue.pop_front();
        System.out.println(testQueue.max()==6);
        // {2, 5}
        testQueue.pop_front();
        System.out.println(testQueue.max()==5);
        // {5}
        testQueue.pop_front();
        System.out.println(testQueue.max()==5);
        // {5, 1}
        testQueue.push_back(1);
        System.out.println(testQueue.max()==5);
    }
}
